package linkedList;

public class LinkedList <E> {

	/**
	 * 关于Node的内部类
	 * (为链表添加虚拟头节点)
	 * @author Administrator
	 *
	 */
	private class Node{
		public E e;
		public Node next;
		
		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e,null);
		}
		
		public Node() {
			this(null,null);
		}
		
		@Override
		public String toString() {
		
			return e.toString();
		}
	}
	
	private Node dummyHead;
	private int size;
	
	public LinkedList() {
		dummyHead = new Node();
		size = 0;
	}
	
	//获取链表元素的个数
	public int getSize() {
		return size;
	}
	
	//链表是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	
	//在链表头添加新的元素
	public void addFirst(E e) {
		add(0,e);
	}
	
	//为链表添加元素
	public void add(int index,E e) {
		Node node = new Node(e);
		//在index之前的位置添加元素
		if(index < 0 || index > size )
			throw new IllegalArgumentException();
		
		Node pre = dummyHead;
		for(int i = 0 ; i < index ; i++)
			//执行完这个循环可以找到size之前位置的元素
			pre = pre.next;
		node.next = pre.next;
		pre.next = node;
		size++;
	}
	
	//在后面添加元素
	public void addLast(E e) {
		add(size,e);
	}
	
	//查找元素
	public E get(int index) {
		if(index < 0 || index >= size)
			throw new IllegalArgumentException();
		Node cur = dummyHead.next;
		for(int i = 0 ; i < index ; i++)
			cur = cur.next;
		return cur.e;
	}
	
	//查找第一个元素
	public E getFirst() {
		return get(0);
	}
	
	//查找最后一个元素
	public E getLast() {
		return get(size - 1);
	}
	
	//修改链表指定位置的值
	public void set(int index, E e) {
		if(index < 0 || index >=size)
			throw new IllegalArgumentException();
		Node cur = dummyHead.next;
		for(int i = 0 ; i < index ; i++)
			cur = cur.next;
		cur.e = e;
	}
	
	// 查找链表中是否有元素e
	public boolean contains(E e) {
		Node cur = dummyHead;
		for(int i = 0 ; i < size ; i++) {
			cur = cur.next;
			if((cur.e).equals(e)) {
				return true;
			}
		}
		return false;
	}
	
	//移除元素
	//移除一定索引位置的元素
	public E remove(int index) {
		if(index < 0 || index >= size)
			throw new IllegalArgumentException();
		Node pre = dummyHead;
		for(int i = 0 ; i < index ; i++) {
			pre = pre.next;
		}
		//开始删除元素
		Node cur = pre.next;
		pre.next = cur.next;
		E ret = cur.e;
		cur.next = null;
		size--;
		return ret;
	}
	
	//从链表中移除第一个元素
	public E removeFirst() {
		return remove(0);
	}
	
	//移除链表最后一个元素
	public E removeLast() {
		return remove(size - 1);
	}
	
	//从链表中删除元素e
	//删除指定值的元素
	public void removeElement(E e) {
		Node prev = dummyHead;
		while(prev != null) {
			if(prev.next.e.equals(e)){
				Node tempNode = prev.next;
				prev.next = tempNode.next;
				tempNode.next = null;
				size--;
				break;
			}
			prev = prev.next;
		}
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("LinkedList-> size:"+size);
		res.append("head[");
		Node cur = dummyHead.next;
		while(cur != null) {
			res.append(cur.e);
			cur = cur.next;
			if(cur != null) {
				res.append(",");
			}
		}
		res.append("]tail");
		return res.toString();
	}
}
